/*
  位数问题 (使用递推的方法求解)
  题目描述
    在所有的 N 位数中，有多少个数中有偶数个数字 3?
    由于结果可能很大，你只需要输出这个答案对 12345 取余的值。
  输入
    输入包含一行，一个数字，不超过 1000。读入一个数 N。
  输出
    输出有多少个数中有偶数个数字 3。
  样例输入
    2
  样例输出
    73
  提示
    样例说明
      在 10 - 99 中
        有 0 个 3 的数有 72 个
        有 2 个 3 的数有 1 个
*/

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;

    cin >> n;
    if (n == 1) {
        cout << 9;  // 有偶数个(0 个) 3 的 1 位数分别是: 0 ~ 2，4 ~ 9, 共计 9 个数
    } else if (n == 2) {
        int a = 1;  // a: 有奇数个 3 的数的个数，当 n == 1 时，a 为 1
        int b = 9;  // b: 有偶数个 3 的数的个数，当 n == 1 时，b 为 9

        /*
          在已知 "n == 1 时，如下 2 种数的统计值" 的情况下,
            偶数个 3 的数的个数 (用变量 b 来表示)
            奇数个 3 的数的个数 (用变量 a 来表示)
          计算出 n == 2 的情况下对应的 2 种数的统计值
            偶数个 3 的数的个数
            奇数个 3 的数的个数

          计算思路:
            在 1 位数的左边插入 1 位数字(1 ~ 9), 就可以得到 1 个新的 2 位数;
            在所有可能的 1 位数的左边分别插入 1 位数字(1 ~ 9)，就可以得到所有可能的 2 位数

            假设:
              n == 1 时，奇数个 3 的数的个数为 a, 偶数个 3 的数的个数为 b,
            那么:
              n == 2 时, 偶数个 3 的数的个数: b * 8 + a * 1
              n == 2 时, 奇数个 3 的数的个数: b * 1 + a * 8
        */
        cout << b * 8 + a * 1;
    } else {
        int a = 17;  // a: 有奇数个 3 的数的个数，当 n == 2 时，a 为 17
        int b = 73;  // b: 有偶数个 3 的数的个数，当 n == 2 时，b 为 73
        int x;

        /*
          在已知 "n == 2 时，如下 2 种数的统计值" 的情况下,
            偶数个 3 的数的个数 (用变量 b 来表示)
            奇数个 3 的数的个数 (用变量 a 来表示)
          计算出 n == 3 的情况下对应的 2 种数的统计值
            偶数个 3 的数的个数
            奇数个 3 的数的个数

          同理, 在已知 "n == 3 时, 2 种数的统计值"的情况下，求出 n == 4 时，这 2 种数的统计值
          依次类推 ...
          在已知 "n == k (k >= 2) 时, 2 种数的统计值"的情况下，求出 n == k + 1 时，这 2 种数的统计值

          计算思路:
            在 k (k >= 2) 位数的最右边插入 1 位数字(0 ~ 9), 就可以得到 1 个新的 k + 1 位数;
            在所有可能的 k (k >= 2) 位数的最右边分别插入 1 位数字(0 ~ 9)，就可以得到所有可能的 k + 1 位数

            假设:
              n == k (k >= 2) 时，奇数个 3 的数的个数为 a, 偶数个 3 的数的个数为 b,
            那么:
              n == k + 1 (k >= 2) 时, 偶数个 3 的数的个数: b * 9 + a * 1
              n == k + 1 (k >= 2) 时, 奇数个 3 的数的个数: b * 1 + a * 9
        */
        for (int i = 3; i <= n; i++) {
            b = b % 12345;
            a = a % 12345;
            x = b * 9 + a * 1;
            a = b * 1 + a * 9;
            b = x;
        }
        b = b % 12345;
        cout << b;
    }

    return 0;
}